[1507.08705] Bidirectional PageRank Estimation: From Average

Accuracy Analysis: We first prove that Undirected-BiPPR returns an unbiased estimate with the desired accuracy:

In an undirected graph G𝐺Gitalic_G, for any source node s𝑠sitalic_s, minimum threshold δ𝛿\deltaitalic_δ, maximum residual r𝑚𝑎𝑥subscript𝑟𝑚𝑎𝑥r_{\text{max}}italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT, relative error ϵitalic-ϵ\epsilonitalic_ϵ, and failure probability p𝑓𝑎𝑖𝑙subscript𝑝𝑓𝑎𝑖𝑙p_{\text{fail}}italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT, Algorithm 2 outputs an estimate π^s[t]subscriptnormal-^𝜋𝑠delimited-[]𝑡\widehat{\mathbf{\pi}}_{s}[t]over^ start_ARG italic_π end_ARG start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] such that with probability at least 1−p𝑓𝑎𝑖𝑙1subscript𝑝𝑓𝑎𝑖𝑙1-p_{\text{fail}}1 - italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT we have: |πs[t]−π^s[t]|≤max⁡{ϵπs[t],2eδ}subscript𝜋𝑠delimited-[]𝑡subscriptnormal-^𝜋𝑠delimited-[]𝑡italic-ϵsubscript𝜋𝑠delimited-[]𝑡2𝑒𝛿\qquad\left\lvert\pi_{s}[t]-\hat{\pi}_{s}[t]\right\rvert\leq\max\{\epsilon\pi_{s}[t],2e\delta\}| italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] - over^ start_ARG italic_π end_ARG start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] | ≤ roman_max { italic_ϵ italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] , 2 italic_e italic_δ }.

The proof follows a similar outline as the proof of Theorem 1111 in [20]. For completeness, we sketch the proof here:

As stated in Algorithm 2, we average over w=cdtrmax/ϵ2δ𝑤𝑐subscript𝑑𝑡subscript𝑟maxsuperscriptitalic-ϵ2𝛿w=cd_{t}r_{\text{max}}/\epsilon^{2}\deltaitalic_w = italic_c italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT / italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT italic_δ walks, where c𝑐citalic_c is a parameter we choose later. Each walk is of length Geometric(α)𝐺𝑒𝑜𝑚𝑒𝑡𝑟𝑖𝑐𝛼Geometric(\alpha)italic_G italic_e italic_o italic_m italic_e italic_t italic_r italic_i italic_c ( italic_α ), and we denote Visubscript𝑉𝑖V_{i}italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT as the last node visited by the ithsuperscript𝑖𝑡ℎi^{th}italic_i start_POSTSUPERSCRIPT italic_t italic_h end_POSTSUPERSCRIPT walk; note that Vi∼πtsimilar-tosubscript𝑉𝑖subscript𝜋𝑡V_{i}\sim\pi_{t}italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∼ italic_π start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT. As defined above, let Xi=rs(Vi)dt/dVisubscript𝑋𝑖subscript𝑟𝑠subscript𝑉𝑖subscript𝑑𝑡subscript𝑑subscript𝑉𝑖X_{i}=r_{s}(V_{i})d_{t}/d_{V_{i}}italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT = italic_r start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT ( italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ) italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT / italic_d start_POSTSUBSCRIPT italic_V start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT end_POSTSUBSCRIPT; the estimate returned by Undirected-BiPPR is:

First, from Eqn. (5), we have that 𝔼[π^s[t]]=πs[t]𝔼delimited-[]subscript^𝜋𝑠delimited-[]𝑡subscript𝜋𝑠delimited-[]𝑡{\mathbb{E}}[\widehat{\pi}_{s}[t]]=\pi_{s}[t]blackboard_E [ over^ start_ARG italic_π end_ARG start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] ] = italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ]. Also, ApproximatePageRank guarantees that for all v𝑣vitalic_v, rs[v]ϵ𝔼[Y]]\epsilon{\mathbb{E}}[Y]] italic_ϵ blackboard_E [ italic_Y ] ] < 2 roman_exp ( - divide start_ARG italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG 3 end_ARG blackboard_E [ italic_Y ] )

For any b>2e𝔼[Y],ℙ[Y>b]≤2−bformulae-sequenceFor any 𝑏2𝑒𝔼delimited-[]𝑌ℙdelimited-[]𝑌𝑏superscript2𝑏\textrm{For any }b>2e{\mathbb{E}}[Y],{\mathbb{P}}[Y>b]\leq 2^{-b}For any italic_b > 2 italic_e blackboard_E [ italic_Y ] , blackboard_P [ italic_Y > italic_b ] ≤ 2 start_POSTSUPERSCRIPT - italic_b end_POSTSUPERSCRIPT

We perform a case analysis based on whether 𝔼[Xi]≥δ𝔼delimited-[]subscript𝑋𝑖𝛿{\mathbb{E}}[X_{i}]\geq\deltablackboard_E [ italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ] ≥ italic_δ or 𝔼[Xi]ϵπs[t]]ℙdelimited-[]subscript^𝜋𝑠delimited-[]𝑡subscript𝜋𝑠delimited-[]𝑡italic-ϵsubscript𝜋𝑠delimited-[]𝑡\displaystyle{\mathbb{P}}\left[\left\lvert\widehat{\pi}_{s}[t]-\pi_{s}[t]\right\rvert>\epsilon\pi_{s}[t]\right]blackboard_P [ | over^ start_ARG italic_π end_ARG start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] - italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] | > italic_ϵ italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] ] ≤ℙ[|X¯−𝔼[Xi]|>ϵ𝔼[Xi]]=ℙ[|Y−𝔼[Y]|>ϵ𝔼[Y]]absentℙdelimited-[]¯𝑋𝔼delimited-[]subscript𝑋𝑖italic-ϵ𝔼delimited-[]subscript𝑋𝑖ℙdelimited-[]𝑌𝔼delimited-[]𝑌italic-ϵ𝔼delimited-[]𝑌\displaystyle\leq{\mathbb{P}}\left[\left\lvert\bar{X}-{\mathbb{E}}[X_{i}]\right\rvert>\epsilon{\mathbb{E}}[X_{i}]\right]={\mathbb{P}}\left[\left\lvert Y-{\mathbb{E}}[Y]\right\rvert>\epsilon{\mathbb{E}}[Y]\right]≤ blackboard_P [ | over¯ start_ARG italic_X end_ARG - blackboard_E [ italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ] | > italic_ϵ blackboard_E [ italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ] ] = blackboard_P [ | italic_Y - blackboard_E [ italic_Y ] | > italic_ϵ blackboard_E [ italic_Y ] ] ≤2exp⁡(−ϵ23𝔼[Y])≤2exp⁡(−c3)≤pfail,absent2superscriptitalic-ϵ23𝔼delimited-[]𝑌2𝑐3subscript𝑝fail\displaystyle\leq 2\exp\left(-\frac{\epsilon^{2}}{3}{\mathbb{E}}[Y]\right)\leq 2\exp\left(-\frac{c}{3}\right)\leq p_{\text{fail}},≤ 2 roman_exp ( - divide start_ARG italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG 3 end_ARG blackboard_E [ italic_Y ] ) ≤ 2 roman_exp ( - divide start_ARG italic_c end_ARG start_ARG 3 end_ARG ) ≤ italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT ,

where the last line holds as long as we choose c≥3ln⁡(2/pfail)𝑐32subscript𝑝failc\geq 3\ln\left(2/p_{\text{fail}}\right)italic_c ≥ 3 roman_ln ( 2 / italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT ).

Suppose alternatively that 𝔼[Xi]2eδ]ℙdelimited-[]subscript^𝜋𝑠delimited-[]𝑡subscript𝜋𝑠delimited-[]𝑡2𝑒𝛿\displaystyle{\mathbb{P}}[\left\lvert\hat{\pi}_{s}[t]-\pi_{s}[t]\right\rvert>2e\delta]blackboard_P [ | over^ start_ARG italic_π end_ARG start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] - italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ] | > 2 italic_e italic_δ ] =ℙ[|X¯−𝔼[Xi]|>2eδ]=ℙ[|Y−𝔼[Y]|>wdtrmax2eδ]absentℙdelimited-[]¯𝑋𝔼delimited-[]subscript𝑋𝑖2𝑒𝛿ℙdelimited-[]𝑌𝔼delimited-[]𝑌𝑤subscript𝑑𝑡subscript𝑟max2𝑒𝛿\displaystyle={\mathbb{P}}[\left\lvert\bar{X}-{\mathbb{E}}[X_{i}]\right\rvert>2e\delta]={\mathbb{P}}\left[\left\lvert Y-{\mathbb{E}}[Y]\right\rvert>\frac{w}{d_{t}r_{\text{max}}}2e\delta\right]= blackboard_P [ | over¯ start_ARG italic_X end_ARG - blackboard_E [ italic_X start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ] | > 2 italic_e italic_δ ] = blackboard_P [ | italic_Y - blackboard_E [ italic_Y ] | > divide start_ARG italic_w end_ARG start_ARG italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT end_ARG 2 italic_e italic_δ ] ≤ℙ[Y>wdtrmax2eδ].absentℙdelimited-[]𝑌𝑤subscript𝑑𝑡subscript𝑟max2𝑒𝛿\displaystyle\leq{\mathbb{P}}\left[Y>\frac{w}{d_{t}r_{\text{max}}}2e\delta\right].≤ blackboard_P [ italic_Y > divide start_ARG italic_w end_ARG start_ARG italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT end_ARG 2 italic_e italic_δ ] .

At this point we set b=2eδw/dtrmax=2ec/ϵ2𝑏2𝑒𝛿𝑤subscript𝑑𝑡subscript𝑟max2𝑒𝑐superscriptitalic-ϵ2b=2e\delta w/d_{t}r_{\text{max}}=2ec/\epsilon^{2}italic_b = 2 italic_e italic_δ italic_w / italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT = 2 italic_e italic_c / italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT and apply the second Chernoff bound. Note that 𝔼[Y]=c𝔼[Xi]/ϵ2δ2e𝔼[Y]𝑏2𝑒𝔼delimited-[]𝑌b>2e{\mathbb{E}}[Y]italic_b > 2 italic_e blackboard_E [ italic_Y ]. We conclude that:

as long as we choose c𝑐citalic_c such that c≥ϵ22elog2⁡1pfail𝑐superscriptitalic-ϵ22𝑒subscript21subscript𝑝failc\geq\frac{\epsilon^{2}}{2e}\log_{2}\frac{1}{p_{\text{fail}}}italic_c ≥ divide start_ARG italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG start_ARG 2 italic_e end_ARG roman_log start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT divide start_ARG 1 end_ARG start_ARG italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT end_ARG. The proof is completed by combining both cases and choosing c=3ln⁡(2/pfail)𝑐32subscript𝑝failc=3\ln\left(2/p_{\text{fail}}\right)italic_c = 3 roman_ln ( 2 / italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT ).□□\quad\square□

Running Time Analysis: The more interesting analysis is that of the running-time of Undirected-BiPPR – we now prove a worst-case running-time bound:

In an undirected graph, for any source node (or distribution) s𝑠sitalic_s, target t𝑡titalic_t with degree dtsubscript𝑑𝑡d_{t}italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT, threshold δ𝛿\deltaitalic_δ, maximum residual r𝑚𝑎𝑥subscript𝑟𝑚𝑎𝑥r_{\text{max}}italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT, relative error ϵitalic-ϵ\epsilonitalic_ϵ, and failure probability p𝑓𝑎𝑖𝑙subscript𝑝𝑓𝑎𝑖𝑙p_{\text{fail}}italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT, Undirected-BiPPR has a worst-case running-time of:

Before proving this result, we first state and prove a crucial lemma from [2]:

Let T𝑇Titalic_T be the total number of push operations performed by ApproximatePageRank, and let dksubscript𝑑𝑘d_{k}italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT be the degree of the vertex involved in the kthsuperscript𝑘𝑡ℎk^{th}italic_k start_POSTSUPERSCRIPT italic_t italic_h end_POSTSUPERSCRIPT push. Then:

Let vksubscript𝑣𝑘v_{k}italic_v start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT be the vertex pushed in the kthsuperscript𝑘𝑡ℎk^{th}italic_k start_POSTSUPERSCRIPT italic_t italic_h end_POSTSUPERSCRIPT step – then by definition, we have that rs(vk)>rmaxdksubscript𝑟𝑠subscript𝑣𝑘subscript𝑟maxsubscript𝑑𝑘r_{s}(v_{k})>r_{\text{max}}d_{k}italic_r start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT ( italic_v start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) > italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT. Now after the local-push operation, the sum residual ‖rs‖1subscriptnormsubscript𝑟𝑠1||r_{s}||_{1}| | italic_r start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT | | start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT decreases by at least αrmaxdk𝛼subscript𝑟maxsubscript𝑑𝑘\alpha r_{\text{max}}d_{k}italic_α italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT. However, we started with ‖rs‖1=1subscriptnormsubscript𝑟𝑠11||r_{s}||_{1}=1| | italic_r start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT | | start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 1, and thus we have ∑k=1Tαrmaxdk≤1superscriptsubscript𝑘1𝑇𝛼subscript𝑟maxsubscript𝑑𝑘1\sum_{k=1}^{T}\alpha r_{\text{max}}d_{k}\leq 1∑ start_POSTSUBSCRIPT italic_k = 1 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_T end_POSTSUPERSCRIPT italic_α italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT italic_d start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ≤ 1. □□\qquad\square□

Note also that the amount of work done while pushing from a node v𝑣vitalic_v is dvsubscript𝑑𝑣d_{v}italic_d start_POSTSUBSCRIPT italic_v end_POSTSUBSCRIPT.

As proven in Lemma 2, the push forward step takes total time O(1/αrmax)𝑂1𝛼subscript𝑟maxO\left(1/\alpha r_{\text{max}}\right)italic_O ( 1 / italic_α italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT ) in the worst-case. The random walks take O(w)=O(1ϵ2rmaxδ/dt)𝑂𝑤𝑂1superscriptitalic-ϵ2subscript𝑟max𝛿subscript𝑑𝑡O(w)=O\left(\frac{1}{\epsilon^{2}}\frac{r_{\text{max}}}{\delta/d_{t}}\right)italic_O ( italic_w ) = italic_O ( divide start_ARG 1 end_ARG start_ARG italic_ϵ start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_ARG divide start_ARG italic_r start_POSTSUBSCRIPT max end_POSTSUBSCRIPT end_ARG start_ARG italic_δ / italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT end_ARG ) time. Thus our total time is

Balancing this by choosing rmax=ϵln⁡1pfailδ/dtsubscript𝑟italic-ϵ1subscript𝑝fail𝛿subscript𝑑𝑡r_{\max}=\frac{\epsilon}{\sqrt{\ln{\frac{1}{p_{\text{fail}}}}}}\sqrt{\delta/d_{t}}italic_r start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT = divide start_ARG italic_ϵ end_ARG start_ARG square-root start_ARG roman_ln divide start_ARG 1 end_ARG start_ARG italic_p start_POSTSUBSCRIPT fail end_POSTSUBSCRIPT end_ARG end_ARG end_ARG square-root start_ARG italic_δ / italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT end_ARG, we get total running-time:

We can get a cleaner worst-case running time bound if we make a natural assumption on πs[t]subscript𝜋𝑠delimited-[]𝑡\pi_{s}[t]italic_π start_POSTSUBSCRIPT italic_s end_POSTSUBSCRIPT [ italic_t ]. In an undirected graph, if we let α=0𝛼0\alpha=0italic_α = 0 and take infinitely long walks, the stationary probability of being at any node t𝑡titalic_t is dtmsubscript𝑑𝑡𝑚\frac{d_{t}}{m}divide start_ARG italic_d start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT end_ARG start_ARG italic_m end_ARG. Thus if πs[t]